{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1, Topic 1, Lab B: Resynchronizing Traces with Dynamic Time Warp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "NOTE: This lab references some (commercial) training material on [ChipWhisperer.io](https://www.ChipWhisperer.io). You can freely execute and use the lab per the open-source license (including using it in your own courses if you distribute similarly), but you must maintain notice about this source location. Consider joining our training course to enjoy the full experience.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**SUMMARY:** *In the last lab, we looked at a simple method for resynchronizing traces: the Sum of Absolute Difference. This technique was enough to defeat the simple jitter between the device triggering and it performing an encryption. In this lab, we'll look at a device with jitter during the actual encryption operation.*\n",
    "\n",
    "*In this lab, we'll look at how jitter-based countermeasures can be overcome by resynchronizing the traces. More specifically, we'll use the sum of absolute difference (SAD) measure that we last looked at early on in SCA101.* \n",
    "\n",
    "**LEARNING OUTCOMES:**\n",
    "* Understanding limitations of SAD resynchronization\n",
    "* Using the dynamic time warp preprocessor\n",
    "\n",
    "**NOTE: DTW is a very slow algorithm. Make sure you have a compiled version of FasterDTW installed, otherwise resynchronization will take a long time**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prerequisites\n",
    "\n",
    "This lab will build upon the last lab: Lab 1_1A. It's recommended that you complete that lab before trying this one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#\n",
    "# Perform the capture, resulting in a project of 1000 jittery traces. See the notebooks to copy your data into!\n",
    "#\n",
    "raise NotImplementedError(\"Add your code here, and delete this.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CPA Against Jittery Traces\n",
    "\n",
    "Again, let's try plotting a few traces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt = cw.plot([])\n",
    "for i in range(10):\n",
    "    plt *= cw.plot(proj.waves[i])\n",
    "plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From afar, these probably don't look to bad. The trace shape is a little weird, but that shouldn't be a problem. Zooming in should reveal that the traces are desynchronized. Again, it probably won't work, but let's try our usual CPA attack. We'll use LASCAR, a very fast side channel analysis library, to speed things up:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chipwhisperer.common.api.lascar as cw_lascar\n",
    "from lascar import *\n",
    "cw_container = cw_lascar.CWContainer(proj, proj.textins, start=None, end=None) #optional start and end args set start and end points for analysis\n",
    "guess_range = range(256)\n",
    "leakage = cw_lascar.sbox_HW_gen\n",
    "cpa_engines = [CpaEngine(\"cpa_%02d\" % i, leakage(i), guess_range) for i in range(16)]\n",
    "session = Session(cw_container, engines=cpa_engines).run(batch_size=50)\n",
    "\n",
    "plt = cw.plot([])\n",
    "key_guess = []\n",
    "for i in range(16):\n",
    "    results = cpa_engines[i].finalize()\n",
    "    xrange = range(len(results[0xD0]))\n",
    "    guess = abs(results).max(1).argmax()\n",
    "    print(\"Best Guess is {:02X} ({:02X}) (Corr = {})\".format(guess, proj.keys[0][i], abs(results).max()))\n",
    "    plt *= cw.plot(results[guess]).opts(color=\"red\")\n",
    "    key_guess.append(guess)\n",
    "    \n",
    "plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nothing! Again, nothing unexpected, but it shows that there's enough jitter here to not just be averaged out...\n",
    "\n",
    "Last lab, we were able to overcome jitter by resynchronizing the traces with a SAD match. Let's try that technique again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chipwhisperer.analyzer as cwa\n",
    "resync_traces = cwa.preprocessing.ResyncSAD(proj)\n",
    "resync_traces.ref_trace = 0\n",
    "resync_traces.target_window = (???, ???)\n",
    "resync_traces.max_shift = ???\n",
    "resync_analyzer = resync_traces.preprocess()\n",
    "plt = cw.plot([])\n",
    "for i in range(10):\n",
    "    plt *= cw.plot(resync_analyzer.waves[i])\n",
    "plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The traces probably look a bit better than before during `subbytes`, but if you zoom in you'll again see that there's lots of jitter here. Try the CPA attack again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chipwhisperer.common.api.lascar as cw_lascar\n",
    "from lascar import *\n",
    "cw_container = cw_lascar.CWContainer(resync_analyzer, proj.textins, start=None, end=None) #optional start and end args set start and end points for analysis\n",
    "guess_range = range(256)\n",
    "leakage = cw_lascar.sbox_HW_gen\n",
    "cpa_engines = [CpaEngine(\"cpa_%02d\" % i, leakage(i), guess_range) for i in range(16)]\n",
    "session = Session(cw_container, engines=cpa_engines).run(batch_size=50)\n",
    "\n",
    "plt = cw.plot([])\n",
    "key_guess = []\n",
    "for i in range(16):\n",
    "    results = cpa_engines[i].finalize()\n",
    "    xrange = range(len(results[0xD0]))\n",
    "    guess = abs(results).max(1).argmax()\n",
    "    print(\"Best Guess is {:02X} ({:02X}) (Corr = {})\".format(guess, proj.keys[0][i], abs(results).max()))\n",
    "    plt *= cw.plot(results[guess]).opts(color=\"red\")\n",
    "    key_guess.append(guess)\n",
    "    \n",
    "plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You'll probably find that you didn't have any luck. That's because this target is inserting multiple delays during the actual encryption itself. This means that shifting traces by a single offset isn't going to be very effective.\n",
    "\n",
    "Luckily, SAD isn't the only way to resyncrhonize traces. ChipWhisperer Analyzer also has support for a technique called [dynamic time warp](https://en.wikipedia.org/wiki/Dynamic_time_warping). The details are much more complicated than with SAD, so we'll skip implementing it ourselves this time. Instead, skip straight to the preprocessing.\n",
    "\n",
    "ChipWhisperer uses a faster approximation for dynamic time warp, which is a very slow algorithm. This comes with a parameter to vary: radius. Higher radii will generally give a better synchronization, but at the cost of a higher processing time. 1 is a good value to start with, but you might have to bump it a bit higher to get a good resync."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "import chipwhisperer.analyzer as cwa\n",
    "resync_traces = cwa.preprocessing.ResyncDTW(proj)\n",
    "resync_traces.ref_trace = 0\n",
    "resync_traces.radius = ???\n",
    "resync_analyzer = resync_traces.preprocess()\n",
    "\n",
    "plt = cw.plot([])\n",
    "for i in range(10):\n",
    "    plt *= cw.plot(resync_analyzer.waves[i])\n",
    "plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These traces are looking a lot better! This technique isn't perfect, but it works a lot better than SAD in this case!\n",
    "\n",
    "Let's try a CPA attack now:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chipwhisperer.common.api.lascar as cw_lascar\n",
    "from lascar import *\n",
    "cw_container = cw_lascar.CWContainer(resync_analyzer, proj.textins, start=None, end=None) #optional start and end args set start and end points for analysis\n",
    "guess_range = range(256)\n",
    "leakage = cw_lascar.sbox_HW_gen\n",
    "cpa_engines = [CpaEngine(\"cpa_%02d\" % i, leakage(i), guess_range) for i in range(16)]\n",
    "session = Session(cw_container, engines=cpa_engines).run(batch_size=50)\n",
    "\n",
    "plt = cw.plot([])\n",
    "key_guess = []\n",
    "for i in range(16):\n",
    "    results = cpa_engines[i].finalize()\n",
    "    xrange = range(len(results[0xD0]))\n",
    "    guess = abs(results).max(1).argmax()\n",
    "    print(\"Best Guess is {:02X} ({:02X}) (Corr = {})\".format(guess, proj.keys[0][i], abs(results).max()))\n",
    "    plt *= cw.plot(results[guess]).opts(color=\"red\")\n",
    "    key_guess.append(guess)\n",
    "    \n",
    "plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert key_guess == list(proj.keys[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusions & Next Steps\n",
    "\n",
    "In this lab, you saw how more complicated jitter can defeat the SAD resynchronization technique we used in the last lab. In response, we used the dynamic time warp preprocessor to perform a better resynchronization and defeat the jitter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "<small>NO-FUN DISCLAIMER: This material is Copyright (C) NewAE Technology Inc., 2015-2020. ChipWhisperer is a trademark of NewAE Technology Inc., claimed in all jurisdictions, and registered in at least the United States of America, European Union, and Peoples Republic of China.\n",
    "\n",
    "Tutorials derived from our open-source work must be released under the associated open-source license, and notice of the source must be *clearly displayed*. Only original copyright holders may license or authorize other distribution - while NewAE Technology Inc. holds the copyright for many tutorials, the github repository includes community contributions which we cannot license under special terms and **must** be maintained as an open-source release. Please contact us for special permissions (where possible).\n",
    "\n",
    "THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.</small>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
